package sm

import "fmt"
import "bytes"
import "strings"

type Transitions map[State]map[int]Transition

type Transition struct { lo, hi int; to States }

type Epsilons map[State]States

type EndStates map[State]int

type SM struct {
  allocated States
  transitions Transitions
  epsilons Epsilons
  endStates EndStates
}

func (x *SM) Epsilon( from State, toAll States ) {
  states, present := x.epsilons[from]
  if present == false {
  	states = make(States)
  	x.epsilons[from] = states
  }
  states.AddAll( toAll )
  for to, _ := range toAll { 
  	all, present := x.epsilons[to] 
  	if present { states.AddAll( all ) } 
 }
}

func (m *SM) EndState( finish State, index int ) {
  m.endStates[finish] = index
}

func (x *SM) Transition( rune int, from, to State ) {
  x.rangeTransition( rune, rune + 1, from, to )
}

func (x *SM) rangeTransition( lo, hi int, from, to State ) {
  z, present := x.transitions[from]
  if present == false { z = make(map[int]Transition); x.transitions[from] = z }
//
  n := len(z)
  z[n] = Transition{lo, hi, make(States).Add(to)}
//  y, present := z[rune]
//  if present == false { y = make(States); z[rune] = y }
//
//  z[rune] = y.Add( to )
}


// TODO turn anyBut into a bunch of ranges. 

func (x *SM) InvertedTransition( anyBut string, from, to State ) {
  // here := len(x.transitions)
  // fmt.Printf( ">> IGNORED: anyBut '%s'\n", anyBut )
  // x.transitions[here] = Transition{from, 0, anyBut, to}
  // HORRIBLE:
  for i := 1; i < 128; i += 1 {
    if strings.Index( anyBut, string(i) ) < 0 {
      x.Transition( i, from, to )
    }
  }
}

func (x *SM) NewState() State {
  result := State(len(x.allocated))
  x.allocated[result] = Null{}
  return result
}

func (x *SM) Display() {
  fmt.Printf( "state machine: \n" )
  fmt.Printf( "  there are %d states\n", len(x.allocated) )
  for state, _ := range x.transitions {
    for rune, _ := range x.transitions[state] {
      fmt.Printf( "  from %v by %c to %v\n", state, rune, x.transitions[state][rune] )
    }
  }
}

func NewSM() *SM {
  return &SM{
    allocated: make(States), 
    transitions: make(Transitions), 
    epsilons: make(Epsilons), 
    endStates: make(EndStates) }
}

func (sm *SM) extendByEpsilons( current States ) {
  toAdd := make(States)
  for state, _ := range current { 
    states, present := sm.epsilons[state]
    if present { toAdd.AddAll( states ) } 
  }
  current.AddAll( toAdd )
}

func (sm *SM) Match( x string ) (int, string) {
  var buffer bytes.Buffer
  start := State(0)
  candidate, limit := -1, 0
  current := make(States).With(start)
  for i, ch := range x {
    sm.extendByEpsilons( current )
    buffer.WriteByte( byte(ch) )
    next := make(States)
    for state, _ := range current { 
      if t, present := sm.transitions[state]; present {
      	for _, transition := range t {
      	  if transition.lo <= ch && ch < transition.hi { next.AddAll( transition.to ) }
      	}
        // if s, present := t[ch]; present { next.AddAll( s ) }
      }
    }
    if next.IsEmpty() {
      break
    } else {
      for state, _ := range next {
        index, present := sm.endStates[state]
        if present { candidate, limit = index, i + 1 }
      }
      current = next
    }
  }
  buffer.Truncate( limit )
  return candidate, buffer.String()
}
